package weekMatch.two_107;

import java.util.Arrays;

public class LeeCode_03 {
    public static void main(String[] args) {
//        System.out.println(minimizeConcatenatedLength(new String[]{"aca", "b", "baa"}));
        System.out.println(minimizeConcatenatedLength(new String[]{"aa","ba","cc","a"}));
//        System.out.println(minimizeConcatenatedLength(new String[]{"aa","ba","a"}));
        System.out.println(minimizeConcatenatedLength(new String[]{"aab","a","acc","abb"}));
    }
    private static int minimizeConcatenatedLength(String[] words) {
        int n = words.length;
        int[][][] memo = new int[n][26][26];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 26; j++) {
                Arrays.fill(memo[i][j], -1);
            }
        }
        int all = 0;
        for (String word : words) {
            all += word.length();
        }
        return all -  dfs(memo, words, 1, words[0].charAt(0) - 'a', words[0].charAt(words[0].length() - 1) - 'a');
    }
    private static int dfs(int[][][] memo, String[] words, int i, int pre, int aft){
        if (i >= words.length){
            return 0;
        }
        if (memo[i][pre][aft] != -1)
            return memo[i][pre][aft];
        String word = words[i];
        int c1 = word.charAt(0) - 'a';
        int c2 = word.charAt(word.length() - 1) - 'a';
        int res = Math.max(dfs(memo, words, i + 1, pre, c2) + (aft == c1 ? 1 : 0),
                dfs(memo, words, i + 1, c1, aft) + (c2 == pre ? 1 : 0));
        memo[i][pre][aft] = res;
        return res;
    }
}